home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / x11 / rpg / crossfir.92 / crossfir / crossfire-0.92.5 / common / re-cmp.c < prev    next >
C/C++ Source or Header  |  1996-07-24  |  12KB  |  529 lines
  1. /*
  2.  * static char *rcsid_player_c =
  3.  *   "$Id: re-cmp.c,v 1.4 1994/03/29 08:26:45 master Exp $";
  4.  */
  5.  
  6.  
  7. /* re-cmp.c
  8.  * Pattern match a string, parsing some of the common RE-metacharacters.
  9.  *
  10.  * This code is public domain, but I would appreciate to hear of
  11.  * improvements or even the fact that you use it in your program.
  12.  *
  13.  * Deliberate BUGS:
  14.  *    - These tokens are not supported: | ( )
  15.  *    - You will get the longest expansion of the _first_ string which
  16.  *    matches the RE, not the longest string which would be the proper
  17.  *    behaviour for a RE-matcher.
  18.  *
  19.  * Author: Kjetil T. Homme <kjetilho@ifi.uio.no> May 1993
  20.  */
  21.  
  22. #include <stdio.h>
  23. #include <stdlib.h>
  24. #include <memory.h>
  25. #include <limits.h>
  26. #include <re-cmp.h>
  27.  
  28. /* Get prototype functions to prevent warnings. */
  29. #if defined (__sun__) && defined(StupidSunHeaders)
  30. #  include <sys/types.h>
  31. #  include <sys/time.h>
  32. #  include "sunos.h"   /* Prototypes for standard libraries, sunos lack those */
  33. #endif
  34.  
  35.  
  36. /*   P r o t o t y p e s
  37.  */
  38. char *re_cmp(char *, char *);
  39. static Boolean re_cmp_step(char *, char *, int, int);
  40. static void re_init(void);
  41. static Boolean re_match_token(uchar, selection *);
  42. static char *re_get_token(selection *, char *);
  43. #ifdef DEBUG2
  44. static void re_dump_sel(selection *);
  45. #endif
  46.  
  47. /*   G l o b a l   v a r i a b l e s
  48.  */
  49. static Boolean        re_init_done = False;
  50. static selection    *re_token[RE_TOKEN_MAX];
  51. static char        *re_substr[RE_TOKEN_MAX];
  52. static unsigned int    re_token_depth;
  53.  
  54. /*   E x t e r n a l   f u n c t i o n
  55.  */
  56.  
  57. /* re-cmp - get regular expression match.
  58.  * Return values: NULL - no match or error in regexp.
  59.  *                pointer to beginning of matching string
  60.  */
  61. char *
  62. re_cmp(char *str, char *regexp) {
  63.     char *next_regexp;
  64.     Boolean once = False;
  65.     Boolean matched;
  66.  
  67.     if (re_init_done == False)
  68.     re_init();
  69.  
  70. #ifdef SAFE_CHECKS
  71.     if (regexp == NULL || str == NULL)
  72.     return NULL;
  73. #endif
  74.     if (*regexp == '^') {
  75.     once = True;
  76.     ++regexp;
  77.     }
  78.     if (*regexp == 0) {
  79.     /* // or /^/ matches any string */
  80.     return str;
  81.     }
  82.  
  83.     next_regexp = re_get_token(re_token[0], regexp);
  84.     re_token_depth = 0;
  85.     re_substr[0] = next_regexp;
  86.  
  87.     matched = re_match_token(*str, re_token[0]);
  88.     if (matched && *next_regexp == 0)
  89.     return str;
  90.  
  91.     /* Apologies for the nearly duplicated code below, hopefully it
  92.      * speeds things up.
  93.      */
  94.     if (once) {
  95.     switch (re_token[0]->repeat) {
  96.         case rep_once:
  97.         if (matched == False)
  98.             return NULL;
  99.         break;
  100.         case rep_once_or_more:
  101.         if (matched == False)
  102.             return NULL;
  103.         if (re_cmp_step(str+1, regexp, 0, 1))
  104.             return str;
  105.         break;
  106.         case rep_null_or_once:
  107.         if (matched == False)
  108.             return re_cmp_step(str, next_regexp, 1, 0) ? str : NULL;
  109.         break;
  110.         case rep_null_or_more:
  111.         if (matched) {
  112.             if (re_cmp_step(str+1, regexp, 0, 1))
  113.             return str;
  114.         } else {
  115.             return re_cmp_step(str, next_regexp, 1, 0) ? str : NULL;
  116.         }
  117.         break;
  118.     }
  119.     return re_cmp_step(str+1, next_regexp, 1, 0) ? str : NULL;
  120.     }
  121.  
  122.     if (matched) {
  123.     switch (re_token[0]->repeat) {
  124.         case rep_once:
  125.         case rep_null_or_once:
  126.         break;
  127.         case rep_once_or_more:
  128.         case rep_null_or_more:
  129.         if (re_cmp_step(str+1, regexp, 0, 1))
  130.             return str;
  131.         break;
  132.     }
  133.     if (re_cmp_step(str+1, next_regexp, 1, 0))
  134.         return str;
  135.     }
  136.     do {
  137.     ++str;
  138.     if (re_cmp_step(str, regexp, 0, 0))
  139.         return str;
  140.     } while (*str);
  141.  
  142.     return NULL;
  143. }
  144.  
  145. /*   A u x i l l i a r y   f u n c t i o n s
  146.  */
  147.  
  148. static Boolean
  149. re_cmp_step(char *str, char *regexp, int slot, int matches) {
  150.     /* str    - string to match
  151.      * regexp    - pattern
  152.      * slot    - number of the token which under consideration
  153.      * matches    - how many times the token has matched
  154.      */
  155.     char *next_regexp;
  156.     Boolean matched;
  157.  
  158. #ifdef DEBUG
  159. /*    fprintf(stderr, "['%s', '%s', %d, %d]\n", str, regexp, slot, matches);*/
  160. #endif
  161.  
  162.     if (*regexp == 0) {
  163.     /* When we reach the end of the regexp, the match is a success
  164.      */
  165.     return True;
  166.     }
  167.  
  168.     /* This chunk of code makes sure that the regexp-tokenising happens
  169.      * only once. We only tokenise as much as we need.
  170.      */
  171.     if (slot > re_token_depth) {
  172.     re_token_depth = slot;
  173.     if (re_token[slot] == NULL)
  174.         re_token[slot] = (selection *) malloc(sizeof(selection));
  175.     next_regexp = re_get_token(re_token[slot], regexp);
  176.     if (next_regexp == NULL) {
  177.         /* Syntax error, what else can we do? */
  178.         return False;
  179.     }
  180.     re_substr[slot] = next_regexp;
  181.     } else {
  182.     next_regexp = re_substr[slot];
  183.     }
  184.  
  185.     matched = re_match_token(*str, re_token[slot]);
  186.     if (matched)
  187.     ++matches;
  188.  
  189.     if (*str == 0)
  190.     return (*next_regexp == 0 || re_token[slot]->type == sel_end);
  191.  
  192.     switch (re_token[slot]->repeat) {
  193.     case rep_once:
  194.         if (matches == 1) {    /* (matches == 1) => (matched == True) */
  195.         return re_cmp_step(str+1, next_regexp, slot+1, 0);
  196.         }
  197.         return False;
  198.     case rep_once_or_more:
  199.         if (matched) {    /* (matched == True) => (matches >= 1) */
  200.         /* First check if the current token repeats more */
  201.         if (re_cmp_step(str+1, regexp, slot, matches))
  202.             return True;
  203.         return re_cmp_step(str+1, next_regexp, slot+1, 0);
  204.         }
  205.         return False;
  206.     case rep_null_or_once:
  207.         /* We must go on to the next token, but should we advance str? */
  208.         if (matches == 0) {
  209.         return re_cmp_step(str, next_regexp, slot+1, 0);
  210.         } else if (matches == 1) {
  211.         return re_cmp_step(str+1, next_regexp, slot+1, 0);
  212.         }
  213.         return False;    /* Not reached */
  214.     case rep_null_or_more:
  215.         if (matched) {
  216.         /* Look for further repeats, advance str */
  217.         if (re_cmp_step(str+1, regexp, slot, matches))
  218.             return True;
  219.         return re_cmp_step(str, next_regexp, slot+1, 0);
  220.         }
  221.         return re_cmp_step(str, next_regexp, slot+1, 0);
  222.     }
  223.     return False;
  224. }
  225.  
  226. static void
  227. re_init(void) {
  228.     int i;
  229.  
  230.     re_token[0] = (selection *) malloc(sizeof(selection));
  231.     for (i = 1; i < RE_TOKEN_MAX; i++)
  232.     re_token[i] = NULL;
  233.  
  234.     re_init_done = True;
  235. }
  236.  
  237. static Boolean
  238. re_match_token(uchar c, selection *sel) {
  239.     switch (sel->type) {
  240.     case sel_any:
  241.         return True;
  242.     case sel_end:
  243.         return (c == 0);
  244.     case sel_single:
  245.         return (c == sel->u.single);
  246.     case sel_range:
  247.         return (c >= sel->u.range.low && c <= sel->u.range.high);
  248.     case sel_array:
  249.         return (sel->u.array[c]);
  250.     case sel_not_single:
  251.         return (c != sel->u.single);
  252.     case sel_not_range:
  253.         return (c < sel->u.range.low && c > sel->u.range.high);
  254.     }
  255.     return False;
  256. }
  257.  
  258. /* re_get_token - get regular expression token
  259.  * Returns the first token found in <regexp> in <sel>
  260.  * Return values: NULL    syntax error
  261.  *                pointer to first character past token.
  262.  */
  263. static char *
  264. re_get_token(selection *sel, char *regexp) {
  265.  
  266. #ifdef SAFE_CHECKS
  267. #   define exit_if_null    if (*regexp == 0) return NULL
  268. #else
  269. #   define exit_if_null
  270. #endif
  271.  
  272.     Boolean quoted = False;
  273.     uchar looking_at;
  274.  
  275. #ifdef SAFE_CHECKS
  276.     if (sel == NULL || regexp == NULL || *regexp == 0)
  277.     return NULL;
  278. #endif
  279.  
  280.     do {
  281.     looking_at = *regexp++;
  282.     switch (looking_at) {
  283.         case '$':
  284.             if (quoted) {
  285.             quoted = False;
  286.             sel->type = sel_single;
  287.             sel->u.single = looking_at;
  288.         } else {
  289.             sel->type = sel_end;
  290.         }
  291.         break;
  292.         case '.':
  293.             if (quoted) {
  294.             quoted = False;
  295.             sel->type = sel_single;
  296.             sel->u.single = looking_at;
  297.         } else {
  298.             sel->type = sel_any;
  299.         }
  300.         break;
  301.         case '[':
  302.             /* The fun stuff... perhaps a little obfuscated since I
  303.          * don't trust the compiler to analyse liveness.
  304.          */
  305.         if (quoted) {
  306.             quoted = False;
  307.             sel->type = sel_single;
  308.             sel->u.single = looking_at;
  309.         } else {
  310.             Boolean neg = False;
  311.             uchar first, last = 0;
  312.  
  313.             exit_if_null;
  314.             looking_at = *regexp++;
  315.  
  316.             if (looking_at == '^') {
  317.             neg = True;
  318.             exit_if_null;
  319.             looking_at = *regexp++;
  320.             }
  321.             first = looking_at;
  322.             exit_if_null;
  323.             looking_at = *regexp++;
  324.             if (looking_at == ']') {
  325.             /* On the form [q] or [^q] */
  326.             sel->type = neg ? sel_not_single : sel_single;
  327.             sel->u.single = first;
  328.             break;
  329.             } else if (looking_at == '-') {
  330.             exit_if_null;
  331.             last = *regexp++;
  332.             if (last == ']') {
  333.                 /* On the form [A-] or [^A-]. Checking for
  334.                  * [,-] and making it a range is probably not
  335.                  * worth it :-)
  336.                  */
  337.                 sel->type = sel_array;
  338.                 memset(sel->u.array, neg, sizeof(sel->u.array));
  339.                 sel->u.array[first] = sel->u.array['-'] = !neg;
  340.                 break;
  341.             } else {
  342.                 exit_if_null;
  343.                 looking_at = *regexp++;
  344.                 if (looking_at == ']') {
  345.                 /* On the form [A-G] or [^A-G]. Note that [G-A]
  346.                  * is a syntax error. Fair enough, I think.
  347.                  */
  348. #ifdef SAFE_CHECK
  349.                 if (first > last)
  350.                     return NULL;
  351. #endif
  352.                 sel->type = neg ? sel_not_range : sel_range;
  353.                 sel->u.range.low = first;
  354.                 sel->u.range.high = last;
  355.                 break;
  356.                 }
  357.             }
  358.             }
  359.             {
  360.             /* The datastructure can only represent a RE this
  361.              * complex with an array.
  362.              */
  363.             int i;
  364.             uchar previous;
  365.  
  366.             sel->type = sel_array;
  367.             memset(sel->u.array, neg, sizeof(sel->u.array));
  368.             if (last) {
  369.                 /* It starts with a range */
  370. #ifdef SAFE_CHECK
  371.                 if (first > last)
  372.                 return NULL;
  373. #endif
  374.                 for (i = first; i <= last; i++) {
  375.                 sel->u.array[i] = !neg;
  376.                 }
  377.             } else {
  378.                 /* It begins with a "random" character */
  379.                 sel->u.array[first] = !neg;
  380.             }
  381.             sel->u.array[looking_at] = !neg;
  382.  
  383.             exit_if_null;
  384.             previous = looking_at;
  385.             looking_at = *regexp++;
  386.  
  387.             /* Add more characters to the array until we reach
  388.              * ]. Quoting doesn't and shouldn't work in here.
  389.              * ("]" should be put first, and "-" last if they
  390.              * are needed inside this construct.)
  391.              * Look for ranges as we go along.
  392.              */
  393.             while (looking_at != ']') {
  394.                 if (looking_at == '-') {
  395.                 exit_if_null;
  396.                 looking_at = *regexp++;
  397.                 if (looking_at != ']') {
  398. #ifdef SAFE_CHECK
  399.                     if (previous > looking_at)
  400.                     return NULL;
  401. #endif
  402.                     for (i = previous+1; i < looking_at; i++) {
  403.                     /* previous has already been set and
  404.                      * looking_at is set below.
  405.                      */
  406.                     sel->u.array[i] = !neg;
  407.                     }
  408.                     exit_if_null;
  409.                 } else {
  410.                     sel->u.array['-'] = !neg;
  411.                     break;
  412.                 }
  413.                 }
  414.                 sel->u.array[looking_at] = !neg;
  415.                 previous = looking_at;
  416.                 exit_if_null;
  417.                 looking_at = *regexp++;
  418.             }
  419.             }
  420.         }
  421.         break;
  422.         case '\\':
  423.             if (quoted) {
  424.             quoted = False;
  425.             sel->type = sel_single;
  426.             sel->u.single = looking_at;
  427.         } else {
  428.             quoted = True;
  429.         }
  430.         break;
  431.         default:
  432.             quoted = False;
  433.         sel->type = sel_single;
  434.         sel->u.single = looking_at;
  435.         break;
  436.     }
  437.     } while (quoted);
  438.  
  439.     if (*regexp == '*') {
  440.     sel->repeat = rep_null_or_more;
  441.     ++regexp;
  442.     } else if (*regexp == '?') {
  443.     sel->repeat = rep_null_or_once;
  444.     ++regexp;
  445.     } else if (*regexp == '+') {
  446.     sel->repeat = rep_once_or_more;
  447.     ++regexp;
  448.     } else {
  449.     sel->repeat = rep_once;
  450.     }
  451.  
  452.     return regexp;
  453. }
  454.  
  455. /*   D e b u g   c o d e
  456.  */
  457. #ifdef DEBUG2 /* compile all with DEBUG also ? hevi@lut.fi */
  458. static void
  459. re_dump_sel(selection *sel) {
  460.     switch(sel->type) {
  461.     case sel_any:
  462.         printf(".");
  463.         break;
  464.     case sel_end:
  465.         printf("$");
  466.         break;
  467.     case sel_single:
  468.         printf("<%c>", sel->u.single);
  469.         break;
  470.     case sel_range:
  471.         printf("[%c-%c]", sel->u.range.low, sel->u.range.high);
  472.         break;
  473.     case sel_array:
  474.         {
  475.         int i;
  476.         printf("[");
  477.         for (i = 0; i < UCHAR_MAX; i++) {
  478.             if (sel->u.array[i]) {
  479.             printf("%c", i);
  480.             }
  481.         }
  482.         printf("]");
  483.         }
  484.         break;
  485.     case sel_not_single:
  486.         printf("[^%c]", sel->u.single);
  487.         break;
  488.     case sel_not_range:
  489.         printf("[^%c-%c]", sel->u.range.low, sel->u.range.high);
  490.         break;
  491.     default:
  492.         printf("<UNKNOWN TOKEN!>");
  493.         break;
  494.     }
  495.     switch(sel->repeat) {
  496.     case rep_once:
  497.         break;
  498.     case rep_null_or_once:
  499.         printf("?");
  500.         break;
  501.     case rep_null_or_more:
  502.         printf("*");
  503.         break;
  504.     case rep_once_or_more:
  505.         printf("+");
  506.         break;
  507.     default:
  508.         printf("<UNKNOWN REP-TOKEN!>");
  509.         break;
  510.     }
  511. }
  512.  
  513. int
  514. main(int argc, char *argv[]) {
  515.     char *re, *m;
  516.     selection sel;
  517.  
  518.     re = re_get_token(&sel, argv[1]);
  519.  
  520.     printf("'%s' -> '%s'\n", argv[1], re);
  521.     re_dump_sel(&sel);
  522.     printf("\n");
  523.     m = re_cmp(argv[2], argv[1]);
  524.     if (m)
  525.     printf("MATCH! -> '%s'\n", m);
  526.     return 0;
  527. }
  528. #endif
  529.